#define _CRT_SECURE_NO_WARNINGS 1
typedef pair<int, int> PII;
class Solution {
    int dx[4] = { 0,0,-1,1 };
    int dy[4] = { -1,1,0,0 };
public:
    void bfs(vector<vector<int>>& heights, queue<PII>& q, vector<vector<int>>& c) {
        int m = heights.size();
        int n = heights[0].size();
        vector<vector<int>> st(m, vector<int>(n));
        while (!q.empty()) {
            int sz = q.size();
            for (int i = 0; i < sz; i++) {
                auto it = q.front();
                q.pop();

                int x = it.first;
                int y = it.second;
                if (st[x][y])continue;
                st[x][y] = 1;
                c[x][y]++;
                //ans.push_back({x,y});

                for (int j = 0; j < 4; j++) {
                    int a = dx[j] + x;
                    int b = dy[j] + y;
                    if (a >= 0 && a < m && b >= 0 && b < n && !st[a][b] && heights[a][b] >= heights[x][y]) {
                        // st[a][b]=1;
                        q.push({ a,b });
                    }
                }

            }
        }
    }
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
        queue<PII> q;
        int m = heights.size();
        int n = heights[0].size();
        vector<vector<int>>ans;
        q.push({ 0,n - 1 });
        q.push({ m - 1,0 });

        vector<vector<int>> c(m, vector<int>(n));
        for (int i = 1; i < n; i++) {
            q.push({ 0,i });
        }
        for (int i = 0; i < m; i++) {
            q.push({ i,0 });
        }
        bfs(heights, q, c);
        for (int i = 0; i < n - 1; i++) {
            q.push({ m - 1,i });
        }
        for (int i = 0; i < m; i++) {
            q.push({ i,n - 1 });
        }
        bfs(heights, q, c);
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // cout<<c[i][j]<<" ";
                if (c[i][j] > 1)ans.push_back({ i,j });
            }
            // cout<<endl;
        }

        return ans;
    }
};